from tools_algorithm import *


class Solution:
    def maxMoves(self, kx: int, ky: int, positions: List[List[int]]) -> int:
        n = len(positions)
        positions.append([kx, ky])
        d = [(1, 2), (-1, 2), (1, -2), (-1, -2), (2, 1), (-2, 1), (2, -1), (-2, -1)]
        h = DefaultDict(dict)
        for id, (a, b) in enumerate(positions):
            h[a][b] = id
        dist = [[0] * (n + 1) for _ in range(n + 1)]

        def g(i, j):
            x1, y1 = positions[i]
            x2, y2 = positions[j]
            ans = 0
            visit = [False] * 2500
            visit[x1 * 50 + y1] = True
            q = [(x1, y1)]
            while True:
                ans += 1
                p = []
                for x, y in q:
                    for a, b in d:
                        xa, yb = x + a, y + b
                        if (
                            xa >= 0
                            and xa < 50
                            and yb >= 0
                            and yb < 50
                            and not visit[xa * 50 + yb]
                        ):
                            if xa == x2 and yb == y2:
                                return ans
                            visit[xa * 50 + yb] = True
                            p.append((xa, yb))
                q = p

        for i in range(n):
            for j in range(i + 1, n + 1):
                t = g(i, j)
                dist[i][j] = t
                dist[j][i] = t

        def f(a, b, c, d):
            return dist[h[a][b]][h[c][d]]

        @cache
        def alice(x, y, limit):
            if limit == 0:
                return 0
            ans = 0
            for i in range(n):
                if limit >> i & 1 == 1:
                    ans = max(
                        ans,
                        bob(positions[i][0], positions[i][1], limit ^ (1 << i))
                        + f(x, y, positions[i][0], positions[i][1]),
                    )
            return ans

        @cache
        def bob(x, y, limit):
            if limit == 0:
                return 0
            ans = inf
            for i in range(n):
                if limit >> i & 1 == 1:
                    ans = min(
                        ans,
                        alice(positions[i][0], positions[i][1], limit ^ (1 << i))
                        + f(x, y, positions[i][0], positions[i][1]),
                    )
            return ans

        return alice(kx, ky, (1 << n) - 1)


s = Solution()
print(s.maxMoves(kx=1, ky=1, positions=[[0, 0]]))
